Linked list cycle

Time: O(N); Space: O(1); easy

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = {ListNode} 3->2->0->-4->None

Output: True

Explanation:

  • There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = {ListNode} 1->2->None

Output: True

Explanation:

  • There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = {ListNode} 1->None

Output: False

Explanation:

  • There is no cycle in the linked list.

Follow up:

  • Can you solve it using O(1) (i.e. constant) memory?

[26]:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

1. Hash Table [O(N),O(N)]

Intuition

To detect if a list is cyclic, we can check whether a node had been visited before. A natural way is to use a hash table.

Algorithm

We go through each node one by one and record each node’s reference (or memory address) in a hash table. If the current node is null, we have reached the end of the list and it must not be cyclic. If current node’s reference is in the hash table, then return true.

[31]:

class Solution1(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False

        nodes = {}
        while head != None:
            if head in nodes:
                return True
            nodes[head] = head
            head = head.next
        return False

[33]:

s = Solution1()

head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next   # not ListNode(2)
assert s.hasCycle(head) == True

head = ListNode(1)
head.next = ListNode(2)
head.next.next = head
assert s.hasCycle(head) == True

head = ListNode(1)
assert s.hasCycle(head) == False

2. Two Pointers [O(N),O(1)]

Intuition

Imagine two runners running on a track at different speed. What happens when the track is actually a circle?

Algorithm

The space complexity can be reduced to O(1) by considering two pointers at different speed - a slow pointer and a fast pointer. The slow pointer moves one step at a time while the fast pointer moves two steps at a time.

If there is no cycle in the list, the fast pointer will eventually reach the end and we can return False in this case.

Now consider a cyclic list and imagine the slow and fast pointers are two runners racing around a circle track. The fast runner will eventually meet the slow runner. Why? Consider this case (we name it case A) - The fast runner is just one step behind the slow runner. In the next iteration, they both increment one and two steps respectively and meet each other.

How about other cases? For example, we have not considered cases where the fast runner is two or three steps behind the slow runner yet. This is simple, because in the next or next’s next iteration, this case will be reduced to case A mentioned above.

[34]:

class Solution2(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False

        slow, fast = head, head.next

        while slow.val != fast.val:
            if not fast or not fast.next:
                return False
            slow, fast = slow.next, fast.next.next
        return True

#         while fast and fast.next:
#             fast, slow = fast.next.next, slow.next
#             if fast is slow:
#                 return True
#         return False

[35]:

s = Solution2()

head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next
assert s.hasCycle(head) == True

head = ListNode(1)
head.next = ListNode(2)
head.next.next = head
assert s.hasCycle(head) == True

head = ListNode(1)
assert s.hasCycle(head) == False

3. Reverse list [O(N),O(1)]

Reverse a linked list, if you get the same head that means the linked List has a cycle otherwise it doesn’t

[36]:

class Solution3(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False

        reverse_head = self.reverseList(head)

        if reverse_head is head:
            return True
        else:
            return False

    def reverseList(self, head):
        new_head = None
        while head:
            tmp = head.next
            head.next = new_head
            new_head = head
            head = tmp
        return new_head

[37]:

s = Solution3()

head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next
assert s.hasCycle(head) == True

head = ListNode(1)
head.next = ListNode(2)
head.next.next = head
assert s.hasCycle(head) == True

head = ListNode(1)
assert s.hasCycle(head) == False